package leetcode.code0440;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

/**
 * 超内存
 * @author CaoYu
 * @date 2021年12月24日
 * @description
 */
public class Solution2 implements IDebug {

	static int[] pos;

	static {
		pos = new int[10];
		pos[0] = 1;
		for (int i = 1; i < 10; i++) {
			pos[i] = pos[i - 1] * 10;
		}
	}

	Node root;

	class Node {
		Node[] n;
		int number;
		int count;

		public Node() {
			this.n = new Node[10];
		}

//		[0,1,10,100,1000,10000,100000,1000000,10000000,100000000,1000000000,]
		public void add(int number, int len) {
			int temp = number;
			int div = pos[len - 1];
			Node node = root;
			while (temp >= 0 && div > 0) {
				int num = temp / div;
				temp %= div;
				div /= 10;
				if (node.n[num] == null) {
					node.n[num] = new Node();
				}
				node = node.n[num];
				node.count += 1;
			}
			node.number = number;
		}

		public int query(int k) {
			int ans = 0;
			for (int i = 1; i < 10; i++) {
				int count = root.n[i].count;
				if (k > count) {
					k -= count;
				} else {
					return this.query(root.n[i], k);
				}
			}
			return ans;
		}

		private int query(Node node, int k) {
			int ans = node.number;
			if (k != 1) {
				k -= 1;
				for (int i = 0; i < 10; i++) {
					int count = node.n[i].count;
					if (k > count) {
						k -= count;
					} else {
						return this.query(node.n[i], k);
					}
				}
			}
			return ans;
		}

	}

	public int findKthNumber(int n, int k) {
		root = new Node();
		int len = 1;
		for (int i = 1; i <= n; i++) {
			if (i >= pos[len]) {
				len += 1;
			}
			root.count += 1;
			root.add(i, len);
		}
		return root.query(k);
	}

	@Override
	public void debug1() {
		HelpDebug.compare(10, this.findKthNumber(13, 2));

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution2 so = new Solution2();
		so.debug1();

	}

}
